package com.wfm.tmp;

import org.junit.Test;

/**
 * 0~9 从0开始走n步能走到 0点
 * 【i,j】=【i-1,j-1】+【i-1，j+1】
 * 需要考虑超过要循环的问题，就是要取余
 * 	    0	1	2	3	4	5	6	7	8	9
 *  0	1	0	0	0	0	0	0	0	0	0
 *  1	0	1	0	0	0	0	0	0	0	1
 *  2	2	0	1	0	0	0	0	0	1	0
 *  3	0	3	0	1	0	0	0	1	0	3
 *  4	6	0	4	0	1	0	1	0	4	0
 */
public class P圆环回原点问题 {

    public int backToOrigin(int n){
        int length = 10;
        int[][] dp = new int[n][length];
        dp[0][0]=1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < length; j++) {
                dp[i][j]=dp[i-1][(j-1+length)%length]+dp[i-1][(j+1)%length];
            }
        }
        return dp[n-1][0];
    }
    @Test
    public void test(){
        int i = backToOrigin(5);
        System.out.println(i);
    }
}
